package leetcode.code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * 给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是  nums[i] 右侧小于 nums[i] 的元素的数量。
 *
 * 示例:
 *
 * 输入: [5,2,6,1]
 * 输出: [2,1,1,0]
 * 解释:
 * 5 的右侧有 2 个更小的元素 (2 和 1).
 * 2 的右侧仅有 1 个更小的元素 (1).
 * 6 的右侧有 1 个更小的元素 (1).
 * 1 的右侧有 0 个更小的元素.
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self
 */
public class 计算右侧小于当前元素的个数 {

    public List<Integer> countSmaller(int[] nums) {
        int len = nums.length;
        int[] res = new int[len];
        for (int i = len-1; i >= 0; i-- ){
            for (int j = i; j < len; j++){
                if (nums[j] < nums[i]) res[i] = res[i]+1;
            }
        }
        return Arrays.stream(res).boxed().collect(Collectors.toList());

    }

    /**
     * 二叉查找
     */
    class Solution {
        public List<Integer> countSmaller(int[] nums) {
            Integer[] ret = new Integer[nums.length];
            for (int i = 0; i < nums.length; i++) {
                ret[i] = 0;
            }
            TreeNode root = null;
            for (int i = nums.length - 1; i >= 0; i--) {
                root = insert(root, new TreeNode(nums[i]), ret, i);
            }
            return Arrays.asList(ret);
        }

        public TreeNode insert(TreeNode root, TreeNode node, Integer[] ret, int i) {
            if (root == null) {
                root = node;
                return root;
            }
            if (root.val >= node.val) { // 注意小于等于插入到左子树，防止多加1
                root.count++;
                root.left = insert(root.left, node, ret, i);
            } else {
                ret[i] += root.count + 1;
                root.right = insert(root.right, node, ret, i);
            }
            return root;
        }
    }

    class TreeNode {
        int val;
        int count;
        TreeNode left;
        TreeNode right;
        TreeNode(int val) {
            this.val = val;
            left = null;
            right = null;
            count = 0;
        }
    }


}
